\section{From bounded-round communication complexity to distributed algorithm lower bounds}\label{sec:communication_complexity}

%\section{The Simulation Theorem}\label{sec:simulation_theorem}


Consider the following problem. There are two parties that have unbounded computational power. Each party receives a $b$-bit string, for some integer $b\geq 1$, denoted by $\bar{x}$ and $\bar{y}$ in $\{0, 1\}^b$. They both want to together compute $f(\bar{x}, \bar{y})$ for some function $f:\{0, 1\}^b\times \{0, 1\}^b\rightarrow \mathbb{R}$. At the end of the computation, the party receiving $\bar{y}$ has to output the value of $f(\bar{x}, \bar{y})$. We consider two models of communication.


\squishlist
\item {\em $r$-round direct communication:} This is a variant of the standard model in communication complexity (see \cite{NisanW93} and references therein). Two parties can communicate via a bidirectional edge of unlimited bandwidth. We call the party receiving $\bar{x}$ {\em Alice}, and the other party {\em Bob}. Two parties communicate in {\em rounds} where each round Alice sends a message (of any size) to Bob followed by Bob sending a message to Alice.
    % only one party send a message (of any size) to the other party.  %At the end of the process, Bob will output $f(\bar{x}, \bar{y})$.

\item {\em Communication through network $\graph$:} Two parties are distinct nodes in a distributed network $\graph$, for some integers $\Gamma$ and $\Lambda$ and real $\kappa$; all networks in $\graph$ have $\Theta(\kappa\Gamma\Lambda^\kappa)$ nodes and a diameter of $\Theta(\kappa\Lambda)$.
    (This network is described below.) We denote the nodes receiving $\bar{x}$ and $\bar{y}$ by $s$ and $t$, respectively. %At the end of the process, $r$ will output $f(\bar{x}, \bar{y})$.
\squishend

We consider the {\em public coin randomized algorithms} under both models. In particular, we assume that all parties (Alice and Bob in the first model and all nodes in $\graph$ in the second model) share a random bit string of infinite length.
%
For any $\epsilon\geq 0$, we say that a randomized algorithm $\mathcal{A}$ is {\em $\epsilon$-error} if for any input, it outputs the correct answer with probability at least $1-\epsilon$, where the probability is over all possible random bit strings.
%
In the first model, we focus on the message complexity, i.e., the total number of bits exchanged between Alice and Bob, denoted by  $R_{\epsilon}^{r-cc-pub}(f)$. In the second model, we focus on the running time, denoted by $R_\epsilon^{\graph, s, t}(f)$.


Before we describe $\graph$ in detail, we note the following characteristics which will be used in later sections. An essential part of $\graph$ consists of $\Gamma$ {\em paths}, denoted by $\cP^1, \ldots, \cP^\Gamma$ and nodes $s$ and $t$ (see Fig.~\ref{fig:graph}). Every edge induced by this subgraph has infinitely many copies. The leftmost and rightmost nodes of each path are adjacent to $s$ and $t$ respectively. Ending nodes on the same side of the path (i.e., leftmost or rightmost nodes) are adjacent to each other.
%
%The following properties of $\graph$ will be proved in Section~\ref{subsec:graph_description}.
%
The following properties of $\graph$ follow from the construction of $\graph$ described in Section~\ref{subsec:graph_description}. 
%
\begin{lemma}\label{lem:graphsize} For any $\Gamma\geq 1$, $\kappa\geq 1$ and $\Lambda\geq 2$, network $\graph$ has $\Theta(\Gamma\kappa\Lambda^\kappa)$ nodes. Each of its path $\cP^i$ has $\Theta(\kappa\Lambda^{\kappa})$ nodes. Its diameter is $\Theta(\kappa\diam)$.
\end{lemma}
\begin{proof}

It follows from the construction of $\graph$ in Section~\ref{subsec:graph_description} that the number of nodes in each path $\cP^i$ is
$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa)$ (cf. Eq.~\eqref{eq:sum_phi'}).
%
\note{The real value is between $2\Lambda^\kappa$ and $2(\Lambda^\kappa+\Lambda^{\lfloor\kappa\rfloor})$}
%
Since there are $\Gamma$ paths, the number of nodes in all paths is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%
Each highway $\cH^i$ has $2\lceil\kappa\rceil\Lambda^i+1$ nodes. Therefore, there are $\sum_{i=1}^{\lfloor\kappa\rfloor} (2\lceil\kappa\rceil\Lambda^i+1)$ nodes in the highways. For $\Lambda\geq 2$, the last quantity is $\Theta(\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor})$.
%
Hence, the total number of nodes is $\Theta(\Gamma\kappa\Lambda^\kappa)$.

To analyze the diameter of $\graph$, observe that each node on any path $\cP^i$ can reach a node in highway $\cH^{\lfloor\kappa\rfloor}$ by traveling through $O(\kappa\Lambda)$ nodes in $\cP^i$. Moreover, any node in highway $\cH^i$ can reach a node in highway $\cH^{i-1}$ by traveling trough $O(\Lambda)$ nodes in $\cH^i$. Finally, there are $O(\kappa\Lambda)$ nodes in $\cH^1$. Therefore, every node can reach any other node in $O(\kappa\Lambda)$ steps by traveling through $\cH^1$. Note that this upper bound is tight since the distance between $s$ and $t$ is $\Omega(\kappa\Lambda)$.
\end{proof}

The rest of this section is devoted to  prove the following theorem, which strengthens Theorem~3.1 in \cite{DasSarmaHKKNPPW10}. It says that if there is a fast $\epsilon$-error algorithm for computing function $f$ on any network $\graph$, then there is a fast bounded-round $\epsilon$-error algorithm for Alice and Bob to compute $f$. Moreover, the number of rounds depends on the diameter of $\graph$ (which is $\Theta(\kappa\diam)$).

% THIS THEOREM HAS B IN THE PARAMETER
%\begin{theorem}\label{thm:cc_to_distributed}
%For any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \{0, 1\}$, for any $b$, if $R_\epsilon^{\graph, s, t}(f) \le \kappa\Lambda^\kappa$ then $f$ can be computed by a $\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}$-round direct communication protocol using at most $4BR_\epsilon^{\graph, s, t}(f)$ communication bits in total.
%%In other words, $$R_{\epsilon}^{\frac{8T_\cA}{\lfloor\kappa\rfloor\Lambda}-cc-pub}(f)\leq 2BR_\epsilon^{G, s, t}(f)\,.$$
%\end{theorem}

\begin{theorem}\label{thm:cc_to_distributed}
For any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \mathbb{R}$, for any $b$, if $R_\epsilon^{\graph, s, t}(f) \le \kappa\Lambda^\kappa$ then $f$ can be computed by a $\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}$-round direct communication protocol using at most $(2\kappa\log{n}) R_\epsilon^{\graph, s, t}(f)$ communication bits in total.
In other words, $$R_{\epsilon}^{\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}-cc-pub}(f)\leq (2\kappa\log{n})R_\epsilon^{\graph, s, t}(f)\,.$$
\end{theorem}



\subsection{Description of $\graph$}\label{subsec:graph_description}
$\graph$ has three parameters, a real $\kappa\geq 1$ and two integers $\Gamma\geq 1$ and $\Lambda\geq 2$.
%Let $\lfloor\kappa\rfloor=\lfloor \kappa\rfloor$ and $\lfloor\kappa\rfloor'=\kappa-\lfloor\kappa\rfloor$.
The two basic units in the construction of $\graph$ are {\em highways} and {\em paths} (see Fig.~\ref{fig:graph}).



%%%%%%%% THIS: Graph \graph %%%%%%%%%%%%%%%



\begin{figure}
  \centering
  \tiny
    {
    \psfrag{A}[c]{$\cH^1$}
    \psfrag{B}[c]{$\cH^2$}
    \psfrag{C}[c]{$\cP^1$}
    \psfrag{D}[c]{$\cP^2$}
    \psfrag{E}[c]{$\cP^\Gamma$}
    %
    \psfrag{F}{$v^1_{-12, 1}$}
    \psfrag{G}{$v^1_{-12, 2}$}
    \psfrag{H}{$v^1_{-\infty}$}
    \psfrag{I}{$v^2_{-12, 1}$}
    \psfrag{J}{$v^2_{-12, 2}$}
    \psfrag{K}{$v^2_{-\infty}$}
    \psfrag{L}{$v^\Gamma_{-12, 1}$}
    \psfrag{M}{$v^\Gamma_{-12, 2}$}
    \psfrag{N}{$v^\Gamma_{-\infty}$}
    %
    \psfrag{O}{$v^1_{12, 2}$}
    \psfrag{P}{$v^2_{12, 2}$}
    \psfrag{Q}{$v^\Gamma_{12, 2}$}
    \psfrag{R}{$v^1_{12, 1}$}
    \psfrag{U}{$v^2_{12, 1}$}
    \psfrag{V}{$v^\Gamma_{12, 1}$}
    \psfrag{W}{$v^1_{\infty}$}
    \psfrag{X}{$v^\Gamma_{\infty}$}
    %
    \psfrag{S}[c]{$s$}
    \psfrag{T}[c]{$t$}
    %
    \psfrag{a}[c]{$h_{-12}^1$}
    \psfrag{b}[c]{$h_{-10}^1$}
    \psfrag{c}[c]{$h_{-2}^1$}
    \psfrag{d}[c]{$h_{0}^1$}
    \psfrag{e}[c]{$h_{2}^1$}
    \psfrag{f}[c]{$h_{10}^1$}
    \psfrag{g}[c]{$h_{12}^1$}
    %
    \psfrag{h}[c]{$h_{-12}^2$}
    \psfrag{i}[c]{$h_{-11}^2$}
    \psfrag{j}[c]{$h_{-10}^2$}
    \psfrag{k}[c]{$h_{-9}^2$}
    \psfrag{l}[c]{$h_{-2}^2$}
    \psfrag{m}[c]{$h_{-1}^2$}
    \psfrag{n}[c]{$h_{0}^2$}
    \psfrag{o}[c]{$h_{1}^2$}
    \psfrag{p}[c]{$h_{2}^2$}
    \psfrag{q}[c]{$h_{9}^2$}
    \psfrag{r}[c]{$h_{10}^2$}
    \psfrag{s}[c]{$h_{11}^2$}
    \psfrag{t}[c]{$h_{12}^2$}
    %
    \psfrag{u}{$S_{9, 1}$}
    \psfrag{v}{$S_{7, 1}$}
    \psfrag{w}{$S_{-9, 5}$}
    \psfrag{x}{$S_{-9, 4}$}
    \psfrag{y}{$M^{\tau+1}(h^1_{-10}, h^1_{-8})$}
    \psfrag{z}{$M^{\tau+1}(h^2_{-10}, h^2_{-9})$}
    %
    %
    %\hspace{-0.05\linewidth}
    \includegraphics[width=\linewidth]{construction.eps}
    }
  \caption{\footnotesize An example of $\graph$ where $\kappa=2.5$ and $\Lambda=2$. The dashed edges (in red) have one copy while other edges have infinitely many copies. Observe that $\phi_{10}=6$ while $\phi'_{10}=4$.}\label{fig:graph}
\end{figure}



\paragraph{Highways.} There are $\lfloor\kappa\rfloor$ highways, denoted by $\cH^1, \cH^2, \ldots, \cH^{\lfloor\kappa\rfloor}$. The highway $\cH^i$ is a path of $2\lceil\kappa\rceil\Lambda^i+1$ nodes, i.e.,
$$V(\cH^i)= \{h_0^i, h_{\pm\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm2\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm3\Lambda^{\lfloor\kappa\rfloor-i}}^i, \dots, h_{\pm\lceil\kappa\rceil\Lambda^i\Lambda^{\lfloor\kappa\rfloor-i}}^i\}\quad\mbox{and,}$$
%
$$E(\cH^i) = \{(h^i_{-(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{-j\Lambda^{\lfloor\kappa\rfloor-i}}), (h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}) \mid 0 \le j <\lceil\kappa\rceil\Lambda^i\}\,.$$
%
We connect the highways by adding edges between nodes of the same subscripts, i.e., for any $0<i\leq \lfloor\kappa\rfloor$ and $-\lceil\kappa\rceil\Lambda^i \le j \le \lceil\kappa\rceil\Lambda^i$, there is an edge between $h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}$ and $h^{i+1}_{j\Lambda^{\lfloor\kappa\rfloor-i}}$.

%\paragraph{Labels and Active Nodes.}
For any $-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor} \leq j\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$, define
%\[\phi(h^{\lfloor\kappa\rfloor}_j)=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
\[\phi_j=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
%
Note that $\phi_j$ can be viewed as the number of nodes in $\cH_1$ with subscripts between $0$ and $j$, i.e.,
%
%Observe that $\phi_j$ is the number of nodes in $\cH_1$ with indices between $0$ and $j$, i.e.,
%
%$$\phi_j=|\{h^1_{j'} \mid 0\leq j'\leq j\}|,~~\forall j\geq 0, ~~~\mbox{and}~~~ \phi_j=|\{h^1_{j'} \mid j\leq j'\leq 0\}|,~~\forall j<0\,.$$
\begin{equation*}
\phi_j=
\begin{cases}
|\{h^1_{j'} \mid 0\leq j'\leq j\}| &\mbox{if $j\geq 0$}\\
|\{h^1_{j'} \mid j\leq j'\leq 0\}| & \mbox{if $j<0$}\,.
\end{cases}
\end{equation*}
%
For any $j\geq 0$, we also define
%$\phi'(h^{\lfloor\kappa\rfloor}_j)$ and $\phi'(h^{\lfloor\kappa\rfloor}_{-j})$ to be
%
%$\max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))$.
%\[\phi'(h^{\lfloor\kappa\rfloor}_j) = \phi'(h^{\lfloor\kappa\rfloor}_{-j}) = \min\left(\phi(h^{k'}_{r}), \max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))\right)\,.\]
%
\[\phi'_j = \phi'_{-j} = \min\left\{\phi_j, \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{j'>j} \phi_{j'})\right\}\,.\]
%
%When the parameters are clear from the context, we use $\phi'_j$ to denote $\phi'(h^{\lfloor\kappa\rfloor}_j)$.
%
We use $\phi'_j$ to specify the number of nodes in the paths (defined next), i.e., each path will have $\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j$ nodes. Note that
\begin{align}
\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa).\label{eq:sum_phi'}
\end{align}


\paragraph{Paths.}
There are $\Gamma$ paths, denoted by $\cP^1, \cP^2, \ldots, \cP^{\Gamma}$. To construct each path, we first construct its subpaths as follows. For each node $h^{\lfloor\kappa\rfloor}_j$ in $\cH^{\lfloor\kappa\rfloor}$ and any $0< i\leq \Gamma$, we create a subpath of $\cP^i$, denoted by $\cP^i_j$, having $\phi'_j$ nodes. Denote nodes in $\cP^i_j$ in order by $v^i_{j, 1}, v^i_{j, 2}, \ldots, v^i_{j, \phi'_j}$. We connect these paths together to form $\cP^i_j$, i.e., for any $j\geq 0$, we create edges $(v^i_{j, \phi'_j}, v^i_{j+1, 1})$ and $(v^i_{-j, \phi'_{-j}}, v^i_{-(j+1), 1})$. Let
$$v^i_{-\infty}=v^i_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}} ~~~\mbox{and}~~~ v^i_{\infty}=v^i_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.$$
These two nodes can be thought of as the leftmost and rightmost nodes of path $\cP^i$. We connect the paths together by adding edges between the leftmost (rightmost, respectively) nodes in the paths, i.e., for any $i$ and $i'$, we add edges $(v^i_{-\infty}, v^{i'}_{-\infty})$ ($(v^i_{\infty}, v^{i'}_{\infty})$, respectively).
%


We connect the highways and paths by adding an edge from each node $h^{\lfloor\kappa\rfloor}_j$ to $v^i_{j, 1}$.
%
We also create nodes $s$ and $t$ and connect $s$ ($t$, respectively) to all nodes $v^i_{-\infty}$ ($v^i_\infty$, respectively).
%
Finally, we make infinite copies of every edge except highway edges, i.e., those in $\cup_{i=1}^{\lfloor\kappa\rfloor} E(\cH^i)$.
%This completes a basic structure of networks in $\graph$. To create different networks in $\graph$, we allow any edge not in $E(\cH^i)$, for any $i$, to be multi-edge.
%
Fig.~\ref{fig:graph} shows an example of $\graph$.

%Observe the following properties of $\graph$.





% THIS FIGURE COMBINES EVERYTHING IN ONE FIGURE
%
%\begin{figure}
%  \centering
%  \tiny
%    {
%    \psfrag{A}[c]{$\cH^1$}
%    \psfrag{B}[c]{$\cH^2$}
%    \psfrag{C}[c]{$\cP^1$}
%    \psfrag{D}[c]{$\cP^2$}
%    \psfrag{E}[c]{$\cP^\Gamma$}
%    %
%    \psfrag{F}{$v^1_{-9, 4}$}
%    \psfrag{G}{$v^1_{-9, 5}$}
%    \psfrag{H}{$v^1_{-\infty}$}
%    \psfrag{I}{$v^2_{-9, 4}$}
%    \psfrag{J}{$v^2_{-9, 5}$}
%    \psfrag{K}{$v^2_{-\infty}$}
%    \psfrag{L}{$v^\Gamma_{-9, 4}$}
%    \psfrag{M}{$v^\Gamma_{-9, 5}$}
%    \psfrag{N}{$v^\Gamma_{-\infty}$}
%    %
%    \psfrag{O}{$v^1_{9, 1}$}
%    \psfrag{P}{$v^2_{9, 1}$}
%    \psfrag{Q}{$v^\Gamma_{9, 1}$}
%    \psfrag{R}{$v^1_{7, 1}$}
%    \psfrag{U}{$v^2_{7, 1}$}
%    \psfrag{V}{$v^\Gamma_{7, 1}$}
%    \psfrag{W}{$v^1_{\infty}$}
%    \psfrag{X}{$v^\Gamma_{\infty}$}
%    %
%    \psfrag{S}[c]{$s$}
%    \psfrag{T}[c]{$t$}
%    %
%    \psfrag{a}[c]{$h_{-10}^1$}
%    \psfrag{b}[c]{$h_{-8}^1$}
%    \psfrag{c}[c]{$h_{-2}^1$}
%    \psfrag{d}[c]{$h_{0}^1$}
%    \psfrag{e}[c]{$h_{2}^1$}
%    \psfrag{f}[c]{$h_{8}^1$}
%    \psfrag{g}[c]{$h_{10}^1$}
%    %
%    \psfrag{h}[c]{$h_{-10}^2$}
%    \psfrag{i}[c]{$h_{-9}^2$}
%    \psfrag{j}[c]{$h_{-8}^2$}
%    \psfrag{k}[c]{$h_{-7}^2$}
%    \psfrag{l}[c]{$h_{-2}^2$}
%    \psfrag{m}[c]{$h_{-1}^2$}
%    \psfrag{n}[c]{$h_{0}^2$}
%    \psfrag{o}[c]{$h_{1}^2$}
%    \psfrag{p}[c]{$h_{2}^2$}
%    \psfrag{q}[c]{$h_{7}^2$}
%    \psfrag{r}[c]{$h_{8}^2$}
%    \psfrag{s}[c]{$h_{9}^2$}
%    \psfrag{t}[c]{$h_{10}^2$}
%    %
%    \psfrag{u}{$S_{9, 1}$}
%    \psfrag{v}{$S_{7, 1}$}
%    \psfrag{w}{$S_{-9, 5}$}
%    \psfrag{x}{$S_{-9, 4}$}
%    \psfrag{y}{$M^{\tau+1}(h^1_{-10}, h^1_{-8})$}
%    \psfrag{z}{$M^{\tau+1}(h^2_{-10}, h^2_{-9})$}
%    %
%    %
%    %\hspace{-0.05\linewidth}
%    \includegraphics[width=\linewidth]{G_Gamma_kappa25_Lambda2_2.eps}
%    }
%  \caption{\footnotesize An example of a network in $\graph$ where $\kappa=2.5$ and $\Lambda=2$. The dashed edges (in red) have one copy while other edges have infinitely many copies. Four boxes show an example of iteration 1 of round 9 in the proof of Theorem~\ref{thm:cc_to_distributed}, when Alice sends messages. Initially, Alice and Bob know $C^{\tau}_{9, 1}$ and $C^\tau_{-9, 5}$, respectively (assuming Alice and Bob already simulate $\cA$ for $\tau$ steps). Then, Alice sends $M^{\tau+1}(h^2_{-10}, h^2_{-9})$ and $M^{\tau+1}(h^1_{-10}, h^1_{-8})$ to Bob. Finally, Alice and Bob compute $C^{\tau+1}_{7, 1}$ and $C^{\tau+1}_{-9, 4}$, respectively.}\label{fig:graph}\label{fig:simulation}
%\end{figure}
%



%\begin{proof}[Proof of Lemma~\ref{lem:graphsize}]
%The number of nodes in each path $\cP^i$ is
%$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa)$ (cf. Eq.~\eqref{eq:sum_phi'}).
%%
%\note{The real value is between $2\Lambda^\kappa$ and $2(\Lambda^\kappa+\Lambda^{\lfloor\kappa\rfloor})$}
%%
%Since there are $\Gamma$ paths, the number of nodes in all paths is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%%
%Each highway $\cH^i$ has $2\lceil\kappa\rceil\Lambda^i+1$ nodes. Therefore, there are $\sum_{i=1}^{\lfloor\kappa\rfloor} (2\lceil\kappa\rceil\Lambda^i+1)$ nodes in the highways. For $\Lambda\geq 2$, the last quantity is $\Theta(\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor})$.
%%
%Hence, the total number of nodes is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%
%To analyze the diameter of $\graph$, observe that each node on any path $\cP^i$ can reach a node in highway $\cH^{\lfloor\kappa\rfloor}$ by traveling through $O(\kappa\Lambda)$ nodes in $\cP^i$. Moreover, any node in highway $\cH^i$ can reach a node in highway $\cH^{i-1}$ by traveling trough $O(\Lambda)$ nodes in $\cH^i$. Finally, there are $O(\kappa\Lambda)$ nodes in $\cH^1$. Therefore, every node can reach any other node in $O(\kappa\Lambda)$ steps by traveling through $\cH^1$. Note that this upper bound is tight since the distance between $s$ and $t$ is $\Omega(\kappa\Lambda)$.
%\end{proof}




\subsection{Terminologies}

For any numbers $i$, $j$, $i'$, and $j'$, we say that $(i', j')\geq (i, j)$ if $i'>i$ or ($i'=i$ and $j'\geq j$).
%
For any $-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}\leq i\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ and $1\leq j\leq \phi'_i$, define the {\em $(i, j)$-set} as
%
%
\begin{equation*}
S_{i, j} =
\begin{cases}
\{h^x_{i'}\ |\ 1\leq x\leq \kappa,\ i'\leq i\}\ \cup\ \{v^x_{i', j'}\ |\  1\leq x\leq \Gamma,\ (i, j)\geq (i', j')\} \cup \{s\}& \text{if $i\geq 0$}\\
\{h^x_{i'}\ |\ 1\leq x\leq \kappa,\ i'\geq i\}\ \cup\ \{v^x_{i', j'}\ |\  1\leq x\leq \Gamma,\ (-i, j)\geq (-i', j')\} \cup \{r\} & \text{if $i<0$}\,.
\end{cases}
\end{equation*}
%
See Fig.~\ref{fig:simulation} for an example. For convenience, for any $i>0$, let $S_{i, 0}=S_{i-1, \phi'_{i-1}}$ and $S_{-i, 0}=S_{-(i-1), \phi'_{-(i-1)}}$, and, for any $j$, let $S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, j}=S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}$ and $S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1, j}=S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}$.

%For convenience, for any $i$, let
%
%\[S_{i, 0}=S_{i-1, \phi'_i} ~~~\mbox{and}~~~ S_{-i, 0}=S_{-i+1, \phi'_{-i}} ~~~\mbox{and}~~~ S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, j}=S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}} ~~~\mbox{and}~~~ S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1, j}=S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.\]



%%%%%%%%%%%%%%%%%%% OLD FIGURE %%%%%%%%%%%%%%%%%%%%%%

%\begin{figure}
%  \centering
%  \scriptsize
%    {
%    \psfrag{A}[c]{$\cH^1$}
%    \psfrag{B}[c]{$\cH^2$}
%    \psfrag{C}[c]{$\cP^1$}
%    \psfrag{D}[c]{$\cP^2$}
%    \psfrag{E}[c]{$\cP^\Gamma$}
%    %
%    \psfrag{F}[c]{$C^{t+1}_{-3, 1}$}
%    \psfrag{H}[c]{$C^t_{-3, 2}$}
%    \psfrag{G}[c]{$C^{t}_{3, 1}$}
%    \psfrag{I}[c]{$C^{t+1}_{1, 1}$}
%    %\psfrag{F}[c]{$S_{-3, 2}$}
%    %\psfrag{H}[c]{$S_{-3, 1}$}
%    %\psfrag{G}[c]{$S_{3, 1}$}
%    %\psfrag{I}[c]{$S_{1, 1}$}
%    \psfrag{S}[c]{$s$}
%    \psfrag{T}[c]{$t$}
%    %
%    \psfrag{a}[c]{$h_{-4}^1$}
%    \psfrag{b}[c]{$h_{-2}^1$}
%    \psfrag{c}[c]{$h_0^1$}
%    \psfrag{d}[c]{$h_2^1$}
%    \psfrag{e}[c]{$h_4^1$}
%    %
%    \psfrag{f}{$h_{-4}^2$}
%    \psfrag{g}{$h_{-3}^2$}
%    \psfrag{h}{$h_{-2}^2$}
%    \psfrag{i}{$h_{0}^2$}
%    \psfrag{j}{$h_{3}^2$}
%    \psfrag{k}{$h_{4}^2$}
%    %
%    \psfrag{l}{$v_{-3, 2}^1$}
%    \psfrag{m}{$v_{-3, 1}^1$}
%    \psfrag{n}{$v_{-2, 1}^1$}
%    \psfrag{o}{$v_{3, 1}^1$}
%    \psfrag{p}{$v_{1, 1}^1$}
%    \psfrag{q}{$M^{t+1}(h^1_{-4}, h^1_{-2})$}
%    \psfrag{r}{$M^{t+1}(h^2_{-4}, h^2_{-3})$}
%    %
%    \includegraphics[width=0.95\linewidth]{G_Gamma_kappa25_Lambda2_simulate_iter1.eps}
%    }
%  \caption{\footnotesize An example of iteration 1 of round 3 when Alice sends messages. Initially, Alice and Bob know $C^{\tau}_{3, 1}$ and $C^\tau_{-3, 2}$, respectively (assuming Alice and Bob already simulate $\cA$ for $\tau$ steps). Then, Alice sends $M^{\tau+1}(h^2_{-4}, h^2_{-3})$ and $M^{\tau+1}(h^1_{-4}, h^1_{-2})$ to Bob. Finally, Alice and Bob compute $C^{\tau+1}_{1, 1}$ and $C^{\tau+1}_{-3, 1}$, respectively.}\label{fig:simulation}
%\end{figure}


Let $\mathcal{A}$ be any {\em deterministic} distributed algorithm run on $\graph$ for computing a function $f$. Fix any input strings $\bar{x}$ and $\bar{y}$ given to $s$ and $t$ respectively. Let $\varphi_\cA(\bar{x}, \bar{y})$ denote the execution of $\mathcal{A}$ on $\bar{x}$ and $\bar{y}$. Denote the {\em state} of the node $v$ at the end of time $\tau$ during the execution $\varphi_\cA(\bar{x}, \bar{y})$ by $\sigma_\cA(v, \tau, \bar{x}, \bar{y})$. Let $\sigma_\cA(v, 0, \bar{x}, \bar{y})$ be the state of the node $v$ before the execution $\varphi_\cA(\bar{x}, \bar{y})$ begins. Note that $\sigma_\cA(v, 0, \bar{x}, \bar{y})$ is independent of the input if $v\notin \{s, t\}$, depends only on $\bar{x}$ if $v=s$ and depends only on $\bar{y}$ if $v=t$. Moreover, in two different executions $\varphi_\cA(\bar{x}, \bar{y})$ and $\varphi_\cA(\bar{x}', \bar{y}')$, a node reaches the same state at time $\tau$ (i.e., $\sigma_\cA(v, \tau, \bar{x}, \bar{y})=\sigma_\cA(v, \tau, \bar{x}', \bar{y}')$) if and only if it receives the same sequence of messages on each of its incoming links.


For a given set of nodes $U=\{v_1, \ldots, v_\ell\}\subseteq V$, a {\em configuration}
%
%%%%%% Remove to save space %%%%%%%%%%%
\[C_\cA(U, \tau, \bar{x}, \bar{y}) = <\sigma_\cA(v_1, \tau, \bar{x}, \bar{y}), \ldots, \sigma_\cA(v_\ell, \tau, \bar{x}, \bar{y})>\]
%
%$C_\cA(U, \tau, \bar{x}, \bar{y})$ = $<\sigma_\cA(v_1, \tau, \bar{x}, \bar{y})$, $\ldots$, $\sigma_\cA(v_\ell, \tau, \bar{x}, \bar{y})>$
%
is a vector of the states of the nodes of $U$ at the end of time $\tau$ of the execution $\varphi_\cA(\bar{x}, \bar{y})$.
%
%
From now on, to simplify notations, when $\cA$, $\bar{x}$ and $\bar{y}$ are clear from the context, we use $C^\tau_{i, j}$ to denote $C_\cA(S_{i, j}, \tau, \bar{x}, \bar{y})$.
%

%%%%%%%%%%%%%%%%%%% FIGURE %%%%%%%%%%%%%%%%%%%%

\begin{figure}
  \centering
  \tiny
    {
    \psfrag{A}[c]{$\cH^1$}
    \psfrag{B}[c]{$\cH^2$}
    \psfrag{C}[c]{$\cP^1$}
    \psfrag{D}[c]{$\cP^2$}
    \psfrag{E}[c]{$\cP^\Gamma$}
    %
    \psfrag{F}{$v^1_{-11, 4}$}
    \psfrag{G}{$v^1_{-11, 5}$}
    \psfrag{H}{$S_{1, 1}$}
    \psfrag{I}{$v^2_{-11, 4}$}
    \psfrag{J}{$v^2_{-11, 5}$}
    \psfrag{K}{$v^2_{-\infty}$}
    \psfrag{L}{$v^\Gamma_{-11, 4}$}
    \psfrag{M}{$v^\Gamma_{-11, 5}$}
    \psfrag{N}{$v^\Gamma_{-\infty}$}
    %
    \psfrag{O}{$v^1_{11, 1}$}
    \psfrag{P}{$v^2_{11, 1}$}
    \psfrag{Q}{$v^\Gamma_{11, 1}$}
    \psfrag{R}{$v^1_{9, 1}$}
    \psfrag{U}{$v^2_{9, 1}$}
    \psfrag{V}{$v^\Gamma_{9, 1}$}
    \psfrag{W}{$S_{-11, 0}=S_{-10, 4}$}
    \psfrag{X}{$v^\Gamma_{\infty}$}
    %
    \psfrag{S}[c]{$s$}
    \psfrag{T}[c]{$t$}
    %
    \psfrag{a}[c]{$h_{-12}^1$}
    \psfrag{b}[c]{$h_{-10}^1$}
    \psfrag{c}[c]{$h_{-2}^1$}
    \psfrag{d}[c]{$h_{0}^1$}
    \psfrag{e}[c]{$h_{2}^1$}
    \psfrag{f}[c]{$h_{10}^1$}
    \psfrag{g}[c]{$h_{12}^1$}
    %
    \psfrag{h}[c]{$h_{-12}^2$}
    \psfrag{i}[c]{$h_{-11}^2$}
    \psfrag{j}[c]{$h_{-10}^2$}
    \psfrag{k}[c]{$h_{-9}^2$}
    \psfrag{l}[c]{$h_{-2}^2$}
    \psfrag{m}[c]{$h_{-1}^2$}
    \psfrag{n}[c]{$h_{0}^2$}
    \psfrag{o}[c]{$h_{1}^2$}
    \psfrag{p}[c]{$h_{2}^2$}
    \psfrag{q}[c]{$h_{9}^2$}
    \psfrag{r}[c]{$h_{10}^2$}
    \psfrag{s}[c]{$h_{11}^2$}
    \psfrag{t}[c]{$h_{12}^2$}
    %
    \psfrag{u}{$S_{11, 1}$}
    \psfrag{v}{$S_{9, 1}$}
    \psfrag{w}{$S_{-11, 6}$}
    \psfrag{x}{$S_{-11, 5}$}
    \psfrag{y}{$M^{8}(h^1_{-12}, h^1_{-10})$}
    \psfrag{z}{$M^{8}(h^2_{-12}, h^2_{-11})$}
    %
    %
    \includegraphics[width=\linewidth]{simulation.eps}
    }
%  \caption{\footnotesize An example of round $9$ in the proof of Theorem~\ref{thm:cc_to_distributed}. Before iteration $I_{9, A, 1}$ begins, Alice and Bob know $C^{6}_{9, 1}$ and $C^6_{-9, 5}$, respectively (since Alice and Bob already simulated $\cA$ for $6$ steps). Then, Alice computes and sends $M^{7}(h^2_{-10}, h^2_{-9})$ and $M^{7}(h^1_{-10}, h^1_{-8})$ to Bob.  Alice and Bob then compute $C^{7}_{7, 1}$ and $C^{7}_{-9, 4}$, respectively, at the end of iteration $I_{9, A, 1}$. After they repeat this process for four more times, i.e. Alice sends $M^{8}(h^2_{-10}, h^2_{-9})$, $M^{9}(h^2_{-10}, h^2_{-9})$, $M^{10}(h^2_{-10}, h^2_{-9})$, $M^{11}(h^2_{-10}, h^2_{-9})$ $M^{8}(h^1_{-10}, h^1_{-8})$, $M^{9}(h^1_{-10}, h^1_{-8})$, $M^{10}(h^1_{-10}, h^1_{-8})$ and $M^{11}(h^1_{-10}, h^1_{-8})$,  Bob will be able to compute $C^{11}_{-9, 0}=C^{11}_{-8, 5}$, respectively. Note that Alice is able to compute $C^8_{5, 1}$, $C^9_{3, 1}$, and $C^{10}_{3, 1}$ without receiving any messages from Bob so she can compute and send the previously mentioned messages.}\label{fig:simulation}
%
  \caption{\footnotesize An example of round $11$ in the proof of Theorem~\ref{thm:cc_to_distributed} (see detail in Example~\ref{ex:protocol}).} \label{fig:simulation}
\end{figure}





\subsection{Proof of Theorem~\ref{thm:cc_to_distributed}}
%\danupon{To do: Highlight the difference from the previous proof}
%
%
Let $G=\graph$. Let $f$ be the function in the theorem statement. Let $\mathcal{A}_\epsilon$ be any $\epsilon$-error distributed algorithm for computing $f$ on $G$. Fix a random string $\bar{r}$ used by $\mathcal{A}_\epsilon$ (shared by all nodes in $G$) and consider the {\em deterministic} algorithm $\mathcal{A}$ run on the input of $\mathcal{A}_\epsilon$ and the fixed random string $\bar{r}$.
%
Let $T_{\mathcal{A}}$ be the worst case running time of algorithm $\mathcal{A}$ (over all inputs).
We only consider $T_\mathcal{A}\leq \kappa\Lambda^{\kappa}$, as assumed in the theorem statement.
%
We show that Alice and Bob, when given $\bar{r}$ as the public random string, can simulate $\mathcal{A}$ using $(2\kappa \log{n})T_\mathcal{A}$ communication bits in $8T_\mathcal{A}/(\kappa\Lambda)$ rounds, as follows. (We provide an example in the end of this section.)



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Rounds, Phases, and Iterations.}
For convenience, we will name the rounds backward, i.e., Alice and Bob start at round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ and proceed to round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1$, $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-2$, and so on.
%
Each round is divided into two {\em phases}, i.e., when Alice sends messages and Bob sends messages (recall that Alice sends messages first in each iteration). Each phase of round $r$ is divided into $\phi'_r$ {\em iterations}. Each iteration simulates one round of algorithm $\cA$.
%
We call the $i^{th}$ iteration of round $r$ when Alice (Bob, respectively) sends messages the {\em iteration $I_{r, A, i}$} ($I_{r, B, i}$, respectively). Therefore, in each round $r$ we have the following order of iterations: $I_{r, A, 1}$, $I_{r, A, 2}$, $\ldots$, $I_{r, A, \phi'_r}$, $I_{r, B, 1}$, $\ldots$, $I_{r, B, \phi'_r}$. For convenience, we refer to the time before communication begins as round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1$ and let $I_{r, A, 0}=I_{r+1, A, \phi'_{r+1}}$ and $I_{r, B, 0}=I_{r+1, B, \phi'_{r+1}}$.


Our goal is to simulate one round of algorithm $\cA$ per iteration. That is, after iteration $I_{r, B, i}$ finishes, we will finish the $(\sum_{r'=r+1}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_{r'}+i)^{th}$ round of algorithm $\cA$. Specifically, we let
%
$$t_r=\sum_{r'=r+1}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_{r'}$$
and our goal is to construct a protocol with properties as in the following lemma.

\begin{lemma}\label{lem:after_iteration} There exists a protocol such that there are at most $\kappa\log n$ bits sent in each iteration and satisfies the following properties. For any $r\geq 0$ and $0\leq i\leq \phi'_r$,
%\squishlist
\begin{enumerate}
\item after $I_{r, A, i}$ finishes, Alice and Bob know $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i}_{-r, \phi'_{-r}-i}$, respectively, and \label{property:alice}
\item after $I_{r, B, i}$ finishes, Alice and Bob know $C^{t_r+i}_{r, \phi'_{r}-i}$ and $C^{t_r+i}_{-r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively. \label{property:bob}
%\squishend
\end{enumerate}
\end{lemma}

\begin{proof}%[Proof of Lemma~\ref{lem:after_iteration}]
We first argue that the properties hold for iteration $I_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, A, 0}$, i.e., before Alice and Bob starts communicating. After round $r=\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ starts, Alice can compute $C^0_{r+1, 0}=C^0_{r+1, 1}=C^0_{r, \phi'_{r}}$ which contains the states of all nodes in $\graph$ except $t$. She can do this because every node except $s$ and $t$ has the same state regardless of the input and the state of $s$ depends only on her input string $\bar{x}$.  Similarly, Bob can compute $C^0_{-(r+1), 0}=C^0_{-(r+1), 1}=C^0_{r, \phi'_{r}}$  which depends only on his input $\bar{y}$.

Now we show that, if the lemma holds for any iteration $I_{r, A, i-1}$ then it also holds for iteration $I_{r, A, i}$ as well. Specifically, we show that if Alice and Bob know $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i-1}_{-r, \phi'_{-r}-(i-1)}$, respectively, then they will know $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i}_{-r, \phi'_{-r}-i}$, respectively, after Alice sends at most $\kappa\log n$ messages.

First we show that Alice can compute $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ without receiving any message from Bob. Recall that Alice can compute $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ if she knows
%
\squishlist
\item $C^{t_r+i-1}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, and
\item all messages sent to all nodes in $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ at time $t_r+i$ of algorithm $\cA$.
\squishend
%
By assumption, Alice knows $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ which implies that she knows $C^{t_r+i-1}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ since $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}\subseteq S_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$.
%
Moreover, observe that all neighbors of all nodes in  $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1},1}$ are in $S_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$. Thus, Alice can compute all messages sent to all nodes in $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ at time $t_r+i$ of algorithm $\cA$. Therefore, Alice can compute $C^{t_r+i}_{r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ without receiving any message from Bob.

Now we show that Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ by receiving at most $\kappa\log n$ bits from Alice and use the knowledge of $C^{t_r+i-1}_{-r, \phi'_{-r}-i+1}$. Note that Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ if he knows
\squishlist
\item $C^{t_r+i-1}_{-r, \phi'_{-r}-i}$, and
\item all messages sent to all nodes in $S_{-r, \phi'_{-r}-i}$ at time $t_r+i$ of algorithm $\cA$.
\squishend
%
By assumption, Bob knows $C^{t_r+i-1}_{-r, \phi'_{-r}-i+1}$ which implies that he knows $C^{t_r+i-1}_{-r, \phi'_{-r}-i}$ since $S_{-r, \phi'_{-r}-i}\subseteq S_{-r, \phi'_{-r}-i+1}$.
%
Moreover, observe that all neighbors of all nodes in $S_{-r, \phi'_{-r}-i}$ are in $S_{-r, \phi'_{-r}-i+1}$, except
%
\begin{quote}
$h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $h^{\lfloor\kappa\rfloor-1}_{-(\lfloor r/\Lambda\rfloor+1)}$, $\ldots$, $h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$.
\end{quote}
%
In other words, Bob can compute all messages sent to all nodes in $S_{-r, \phi'_{-r}-i}$ at time $t_r+i$ except
%
\begin{quote}
$M^{t_r+i}(h^{\lfloor\kappa\rfloor}_{-(r+1)}, h^{\lfloor\kappa\rfloor}_{-r})$, $\ldots$, $M^{t_r+i}(h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}, h^{\lfloor\kappa\rfloor-i}_{-\lfloor r/\Lambda^i\rfloor})$, $\ldots$, $M^{t_r+i}(h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}, h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor})$
\end{quote}
%
where $M^{t_r+i}(u, v)$ is the message sent from $u$ to $v$ at time $t_r+i$ of algorithm $\cA$. Observe further that Alice can compute these messages because she knows $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ which contains the states of
%
$h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $\ldots$, $h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$
%
at time $t_r+i-1$. (In particular, $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ is a superset of $C^{t_r+i-1}_{0, 1}$ which contains the states of $h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$.) So, Alice can send these messages to Bob and Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ at the end of the iteration. Each of these messages contains at most $\log n$ bits since each of them corresponds to a message sent on one edge. Therefore, Alice sends at most $\kappa \log n$ bits to Bob in total. This shows the first property.


After Alice finishes sending messages, the two parties will switch their roles and a similar protocol can be used to show that the second property, i.e., if the lemma holds for any iteration $I_{r, B, i-1}$ then it also holds for iteration $I_{r, B, i}$ as well. That is, if Alice and Bob know $C^{t_r+i-1}_{r, \phi'_{r}-(i-1)}$ and $C^{t_r+i-1}_{-r+(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively, then Bob can send $\kappa \log n$ bits to Alice so that they can compute $C^{t_r+i}_{r, \phi'_{r}-i}$ and $C^{t_r+i}_{-r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%Before we describe a protocol that satisfies Lemma~\ref{lem:after_iteration}, we first prove Theorem~\ref{thm:cc_to_distributed}, assuming this lemma.

%We are now ready to prove Theorem~\ref{thm:cc_to_distributed}.

%\begin{proof}[Proof of Theorem~\ref{thm:cc_to_distributed}]% assuming Lemma~\ref{lem:after_iteration}]
Let $P$ be the protocol as in Lemma~\ref{lem:after_iteration}. Alice and Bob will run protocol $P$ until round $r'$, where $r'$ is the largest number such that $t_{r'}+\phi'_{r'}\geq T_\cA$.
%
Lemma~\ref{lem:after_iteration} implies that after iteration $I_{r', B, T_\cA-t_{r'}}$, Bob knows $C^{t_{-r'}+T_\cA-t_{r'}}_{-r', \phi'_{-r'}-T_\cA+t_{r'}}=C^{T_\cA}_{-r', \phi'_{-r'}-T_\cA+t_{r'}}$ (note that $\phi'_{-r'}-T_\cA+t_{r'}\geq 0$).
%
%Therefore, after round $r'$, Alice and Bob know $C^{T_\cA}_{r', \phi'_{r'}}$ and $C^{T_\cA}_{-r', \phi'_{-r'}}$, respectively.
%
In particular, Bob knows the state of node $t$ at time $T_\cA$, i.e., he knows $\sigma_\cA(t, T_\cA, \bar{x}, \bar{y})$. Thus, Bob can output the output of $\cA$ which is output from $t$.

Since $\mathcal{A}_\epsilon$ is $\epsilon$-error, the probability (over all possible shared random strings) that $\mathcal{A}$ outputs the correct value of $f(\bar{x}, \bar{y})$ is at least $1-\epsilon$. Therefore, the communication protocol run by Alice and Bob is $\epsilon$-error as well. The number of rounds is bounded as in the following claim.

\begin{claim}
If algorithm $\cA$ finishes in time $T_\cA\leq \lceil\kappa\rceil\Lambda^\kappa$ then $r'>\lceil\kappa\rceil\Lambda^\kappa-8T_\cA/(\lceil\kappa\rceil\Lambda)$. In other words, the number of rounds Alice and Bob need to simulate $\cA$ is $8T_\cA/(\lceil\kappa\rceil\Lambda)$
%If algorithm $\cA$ finishes in time $T_\cA\leq \Lambda^\kappa$, then the number of rounds Alice and Bob need to simulate $\cA$ is $8T_\cA/(\lceil\kappa\rceil\Lambda)$. %In other words, $r'>\Lambda^\kappa-8T_\cA/\Lambda$
\end{claim}
\begin{proof}
Let $R^*=8T_\cA/(\lceil\kappa\rceil\Lambda)$ and let $r^*=\Lambda^{\lfloor\kappa\rfloor}-R^*+1$. Assume for the sake of contradiction that Alice and Bob need more than $R^*$ rounds. This means that $r'<r^*$.
%
%for each round $r$, they simulate $\cA$ for $\phi'_r$ steps. Thus, the total number of steps of $\cA$ that are simulated by Alice and Bob up to round $r^*$ is
%
%$\sum_{r=r^*}^{\Lambda^{\lfloor\kappa\rfloor}} \phi'_r$.
%
%
Alice and Bob requiring more than $R^*$ rounds implies that %$\sum_{r\geq r^*} \phi'_r < T_\cA$ which is at most $\Lambda^\kappa$.
%
%$$\sum_{r=r^*}^{\Lambda^{\lfloor\kappa\rfloor}} \phi'_r < T_\cA\leq \Lambda^\kappa\,.$$
\begin{align}
\sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_r = t_{r^*}+\phi'_{r^*} < T_\cA \leq \lceil\kappa\rceil\Lambda^\kappa\,.\label{eq:round_bound}
\end{align}
%
It follows that for any $r\geq r^*$,
\begin{align*}
\phi'_r &= \min\left(\phi(h^{k'}_{r}), \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{r'>r} \phi_{r'})\right) &&\mbox{(by definition of $\phi'_r$)}\\
&= \phi_r &&\mbox{(because $\sum_{r\geq r^*} \phi'_r< \lceil\kappa\rceil\Lambda^\kappa$)}\\
&= \left\lfloor \frac{r}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor +1 &&\mbox{(by definition of $\phi_r$).}
\end{align*}
%
%
Therefore, the total number of steps that can be simulated by Alice and Bob up to round $r^*$ is
\begin{align*}
\sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_r & = \sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \left(\left\lfloor \frac{r}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor +1\right)\\
&\geq \Lambda^{\lfloor\kappa\rfloor-1} \sum_{i=1}^{\lfloor R^*/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor} (\lceil\kappa\rceil\Lambda-i)\\
&\geq \Lambda^{\lfloor\kappa\rfloor-1} \cdot \frac{\lfloor R^*/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor (\lceil\kappa\rceil\Lambda-1)}{2}\\
&\geq \frac{R^*\lceil\kappa\rceil\Lambda}{8}\\
&\geq T_\cA
\end{align*}
%
contradicting Eq.~\eqref{eq:round_bound}.
\end{proof}

%In other words, $r'>\Lambda^\kappa-8T_\cA/\Lambda\geq 0$. Thus,
%

Since there are at most $\kappa \log n$ bits sent in each iteration and Alice and Bob runs $P$ for $T_\cA$ iterations, the total number of bits exchanged is at most $(2\kappa\log n)T_\mathcal{A}$. This completes the proof of Theorem~\ref{thm:cc_to_distributed}.
%\end{proof}

%\paragraph{Example}
\begin{example}\label{ex:protocol}
Fig.~\ref{fig:simulation} shows an example of the protocol we use above. Before iteration $I_{11, A, 1}$ begins, Alice and Bob know $C^{7}_{11, 1}$ and $C^7_{-11, 5}$, respectively (since Alice and Bob already simulated $\cA$ for $\phi'_{12}=7$ steps in round $12$). Then, Alice computes and sends $M^{8}(h^2_{-12}, h^2_{-11})$ and $M^{8}(h^1_{-12}, h^1_{-10})$ to Bob.  Alice and Bob then compute $C^{8}_{11, 1}$ and $C^{8}_{-11, 6}$, respectively, at the end of iteration $I_{11, A, 1}$. After they repeat this process for five more times, i.e. Alice sends
%
$$M^{9}(h^2_{-12}, h^2_{-11}), M^{10}(h^2_{-12}, h^2_{-11}), \ldots, M^{13}(h^2_{-12}, h^2_{-11}), ~~~\mbox{and}~~~$$
$$M^{9}(h^1_{-12}, h^1_{-10}), M^{10}(h^1_{-12}, h^1_{-10}), \ldots, M^{13}(h^1_{-12}, h^1_{-10})\,,$$
%
Bob will be able to compute $C^{13}_{-11, 0}=C^{13}_{-10, 4}$. Note that Alice is able to compute $C^8_{9, 1}$, $C^9_{7, 1}$, $\ldots$, $C^{12}_{1, 1}$ without receiving any messages from Bob so she can compute and send the previously mentioned messages to Bob.
\end{example}











